1. Field of the Invention
The present invention relates generally to methods and apparatuses for routing data (referred to as "packets") from a source station to a destination station. More specifically, the invention relates to methods and apparatuses for creating and dismantling a temporary transit path between two routers of a subnetwork. The packets may then travel from the source station along one or more of the temporarily created transit paths to the destination station.
2. Description of the Related Art
One type of network that is used for transmitting data packets is referred to as a connection-oriented network. A connection-oriented network provides mechanisms for a source station to send data packets along a specific path to a destination station. In contrast, a connectionless network (e.g., the Internet) does not provide specific routes, but rather sends data through various paths that eventually reach the destination station. The connection-oriented network is less likely to lose related data packets than the connectionless network. The data packets in a connection-oriented network are typically sent over either a temporary transit path or a permanent transit path. For example, in an ATM (asynchronous transfer mode) or X.25 network, a temporary transit path in the form of a switched virtual circuit (SVC) may be created, or a permanent transit path in the form of an existing permanent virtual circuit (PVC) may be utilized.
FIG. 1A is a diagrammatic representation of a conventional connection-oriented subnetwork 132. As shown, the subnetwork 132 includes a plurality of routers A (118), B (116), and C (108). The subnetwork 132 also includes a source station 126 (a host or router) that is associated with the subnetwork 132 through router A and a destination station 102 (a host or router) that is associated with the subnetwork 132 through router C 108.
A particular router is defined as a member of a subnetwork when the particular router is capable of communicating with other routers within the subnetwork. For example, within a non-broadcast, multi-access (NBMA) subnetwork, routers that have common network identifiers are capable of communicating with each other within the same NBMA subnetwork. For example, each of the routers A, B, and C may have a common network identifier. Thus, routers A, B, and C may communicate with each other to form the subnetwork 132.
Data packets may be transmitted from the source station 126 to the destination station (or visa versa) by utilizing the Next Hop Resolution Protocol (NHRP) for NBMA subnetworks. Specifically, NHRP may be used by a source station's router to determine the addresses of the "next hop" towards a destination station. If the destination station is a member of the same subnetwork as the source station, the next hop is the destination station or the destination station's router. After the next hop is determined, a switched virtual circuit (SVC) is setup between the source station's router and the next hop.
An SVC is a specific type of temporary transit path between two routers or hosts that may be created and dismantled within the connection-oriented subnetwork. In other words, a source station may setup and hang-up a call to a destination station or destination station's router as needed. In contrast, a permanent virtual circuit (PVC) permanently couples two routers or hosts together. That is, a transit path for data communication is permanently set up between two routers or hosts.
As shown, when data packets are sent from the source station 126 to the destination station 102, router A may utilize NHRP to send out a next hop request packet. The request packet travels along PVC's to the destination station 102. Specifically, the request packet travels along PVC 122 to router B, and router B forwards the request packet along PVC 120 to router C, which is associated with the destination station 102. Since router C is coupled to the destination station 102, it is the "next hop" router. Thus, router C sends back a next hop reply to the source station 126 in response to the request packet. An SVC 124 is then setup between router A and C thereby bypassing router B.
By default, NHRP is set up to determine the next hop and create an SVC for each data packet that is sent between a source station and a destination station. However, this default setup has the disadvantage of utilizing significant resources, such as time and memory, to create unnecessary SVC's. An alternative to using the NHRP default is to configure the source station's router to send a next hop request only when a specific number of data packets have been sent from the source station to the destination station through the PVC's. Thus, an SVC would only be created when the packet quantity reaches a significant level. That is, an SVC would be created after a specific number of packets were sent from the source station to the destination station.
FIGS. 2A and 2B are flowcharts illustrating a conventional NHRP process 200 for creating an SVC between a source router and a destination router after a specific number of packets are transmitted. Initially, in operation 202 a count variable is set to zero. Next, a first packet is sent by a permanent virtual circuit (PVC) in operation 204. After the first packet is sent, it is then determined whether there are any more packets to be sent in operation 206. If more packets need to be sent, in operation 208 the count variable is incremented by one. On the other hand, if there are no more packets, the process 200 ends after completion of operation 206.
After the count variable is incremented in operation 208, it is then determined whether the count variable is greater than a predetermined value in operation 210. The predetermined value is set to a value that indicates that a significant number of data packets have traveled from the source to the destination. If the count variable is not greater than the predetermined value, a next packet is sent by PVC in operation 212. However, if the count variable is greater than the predetermined value, a switched virtual circuit (SVC) is created in operation 214 (continued at "A" in FIG. 2B). After the SVC is created, the next packet is sent by SVC in operation 216.
In operation 218, it is determined whether there are any more packets to be sent over the network. This determination operation also typically includes waiting for a predetermined period of time. This period of time is to allow a minimum amount of idle time between data packet transmissions before the SVC is destroyed. If there are more packets to be sent, operation 216 is repeated and a next packet is sent by SVC. Operation 216 is repeated for all remaining packets. When there are no more packets to be sent, the SVC is dismantled in operation 220. The process 200 ends after tearing down the SVC.
Although the above described process 200 is preferable to using the default NHRP process, wherein an SVC is created for each packet, the process 200 is still likely to result in the creation of unnecessary SVC's. For example, if data is being transmitted at a relatively slow rate (e.g., typing on a keyboard), the PVC's may be sufficient for this purpose, and an SVC is not needed. Specifically, 100 packets may be sent over an hour to the destination if the destination is not popular, or may be sent in a second (such as during a file transfer). If an SVC is setup after 99 packets are sent to the destination, an SVC is needlessly created for the 100th packet for the 100 packets per hour case and not created soon enough for the 100 packets per second case.
In view of the foregoing, there is a need for methods and apparatuses for efficiently creating a temporary transit path between a source and next hop that is traffic dependent. Specifically, there is a need for a method to determine when to set up or tear down such a temporary transit path so that temporary trasit paths are set up when they are needed and torn down when they are no longer needed.